Memory de-duplication allows a single physical page of memory to be shared by multiple virtual pages of memory that have identical content across different virtual machines (VMs) running under the same hypervisor. Since fewer physical pages are needed to back the same number of virtual pages, less real memory is required to support the same application load. A related technique is often used within a single operating system instance in order to share physical pages backing virtual pages for individual processes.
The potential savings in total memory required has spurred some operating system designs to implement de-duplication. Existing implementations rely on scanning pages either in the background, or when directed, against the rest of the pages in the system in order to find ones that are the same. These operating system designs support hints as to what pages might be good candidates for de-duplication such that these pages are either compared immediately against the rest of the pages in the system or on a priority basis. With or without hints, matches are found though a search against all other pages in the set being considered for de-duplication. Even in operating systems where de-duplication is not supported, mechanisms are typically in place in order to try to share pages across multiple VMs.
The cost of scanning all pages is not insignificant, and existing implementations reflect this cost. For example, some operating systems defer scanning pages until they have “settled” (i.e., reached a steady state) for a period of time (e.g., minutes), while other operating systems choose not to implement de-duplication at all. The cost can also be a significant issue for some computing platforms, in particular, platforms where customers are charged based on CPU cycles.
While the hints in existing implementations can give priority to some pages in terms of scanning, they do not reduce the overall cost because the pages are still scanned against the rest of the pages in the set being considered for de-duplication. The existing approach of scanning through all pages to find duplicates also becomes less effective as page sizes grow since the chance of a match on a per page basis is lower. As a result of this problem, some hypervisors which support de-duplication defer the process for large pages until the system is already under memory pressure. In these cases, one cannot assess the benefits that will be achieved when pages are de-duplicated making it harder to figure out and provision the amount of memory required.
Thus, existing de-duplication implementations include, but are not limited to, one or more of the following drawbacks: (i) without hints, duplicates are not found immediately because pages are allowed to settle before they are considered for de-duplication; (ii) there may be a delay from the start of scanning before duplicates are found because many pages may have to be compared before the matching pages are found; (iii) CPU cycles are consumed comparing pages that are not matches; (iv) de-duplication may be deferred until the system is under memory pressure, making it harder to recover in time to avoid performance degradations; and (v) pages may not be de-duplicated if there is no memory pressure, making it more difficult to figure out and provision the amount of memory required.